Bubble sort.md (465B)
1 +++ 2 title = 'Bubble sort' 3 +++ 4 # Bubble sort 5 "brute force" 6 1. compare adjacent elements: if current is bigger than next, swap 7 2. compare next adjacent elements 8 3. repeat until go through all and no swaps have been made 9 10 ## performance 11 12 a list with n elements: need n-1 comparisons for first pass, n-2 for second pass, etc. 13 14 number of key comparisons = (n-1) + (n-1) + (n-3) … + 1 = n(n-1)/2 15 16 ## complexity 17 18 - Best case: O(n) 19 - Worst case: O(n²) 20 - Average: O(n²)